package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/20 22:45
 */
public class No204_计数质数 {
    public static void main(String[] args) {
        Solution204 solution204 = new Solution204();
        int i = solution204.countPrimes(20);
        System.out.println(i);
    }
}

class Solution204 {
    public int countPrimes(int n) {
        //筛除法
        //n+1从1开始当成1
        boolean[] primes = new boolean[n + 1];//false,代表素数
        if (n <= 2) {
            return 0;
        }
        for (int i = 2; i < n; i++) {
            //因为2是素数,排除2
            if (i != 2 && i % 2 == 0) {
                continue;
            }
            if (!primes[i]) {
                //倍数置true
                for (int j = i * 2; j <= n; j += i) {
                    primes[j] = true;
                }
            }
        }

        //统计个数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!primes[i]) {
                count++;
            }
        }
        return count;
    }
}


    //public int countPrimes(int n) {
    //    //无脑暴力
    //    int count = 0;
    //    for (int i = 2; i < n; i++) {
    //        if (isPrime(i)) {
    //            count++;
    //        }
    //    }
    //    return count;
    //}
    //
    ////判断data是不是质数
    //public boolean isPrime(int data) {
    //    if (data == 2) {
    //        return true;
    //    }
    //    for (int i = 2; i <= Math.sqrt(data); i++) {
    //        if (data % i == 0) {
    //            return false;
    //        }
    //    }
    //    return true;
    //}